﻿//给定一个正整数n，请找出最少个数的完全平方数，使得这些完全平方数的和等于n。
//完全平方指用一个整数乘以自己例如1 * 1，2 * 2，3 * 3等，依此类推。
//若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。
//例如:1，4，9，和16都是完全平方数，但是2，3，5，8，11等等不是
//
//数据范围 :1≤n≤10^4
//​
//输入描述：
//	仅一行，输入一个正整数 n
//输出描述：
//	按题目要求输出完全平方数之和为n的最少个数
//
//输入：
//	5
//输出：
//	2
//说明：
//	1 + 4 = 5
//
//输入：
//	8
//输出：
//	2
//说明：
//	4 + 4 = 8
//
//输入：
//	9
//输出：
//	1
//说明：
//	3^2 = 9

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e4 + 10;
int n;
int dp[N];
int main() {
    cin >> n;
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i * i <= n; i++) {
        for (int j = i * i; j <= n; j++) {
            dp[j] = min(dp[j], dp[j - i * i] + 1);
        }
    }
    cout << dp[n] << endl;
    return 0;
}
